package com.mamingchao.basic.swardToOffer.zero;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * 给定一个字符串类型的数组arr,求其中出现次数最多的前K个
 *
 * 两步：
 * 1、遍历字符串数组，存放到一个map中；key为 字符char， value是该字符的出现次数累计值
 * 2、使用一个大小为k的小根堆；遍历Map，map中的值 跟堆顶的值对比；如果比堆顶的值大，则poll掉 堆顶的数据，然后把map中的这个值push进去
 *    如果map中的值，比堆顶的值小，直接continue,check下一个
 */
public class TopK {

    public static void main(String[] args) {

        final int k = 3;
        String[] arr = {"a","b","c","d","b","e","b","e","e","a","b"};
        PriorityQueue<InnerItem> topK = getTopK(arr,k);
        while (!topK.isEmpty()){
            System.out.println(topK.poll());
        }
    }


    private static PriorityQueue<InnerItem> getTopK(String[] arr, int k){
        HashMap<String, Integer> map = new HashMap<>(arr.length);
        for (int i = 0; i < arr.length; i++) {

            // map.computeIfPresent(arr[i], (k, v) -> v + 1);
            // map.putIfAbsent(arr[i], 1);

            map.merge(arr[i], 1, Integer::sum);

            // if (map.containsKey(arr[i])){
            //     map.put(arr[i], map.get(arr[i]) + 1);
            // } else {
            //     map.put(arr[i],1);
            // }
        }


        PriorityQueue<InnerItem> minRootHeap = new PriorityQueue<>(k, (o1, o2) -> Integer.compare(o1.getValue(), o2.getValue()));
        for(Map.Entry<String, Integer> entry : map.entrySet()) {
            if (minRootHeap.size() < k ) {
                minRootHeap.add(new InnerItem(entry.getKey(), entry.getValue()));
            } else {
                InnerItem topOne = minRootHeap.peek();
                // 如果当前值比堆顶的值大，则poll掉堆顶的数据，然后把当前值push进去
                if (topOne.getValue() < entry.getValue()) {
                    minRootHeap.poll();
                    minRootHeap.add(new InnerItem(entry.getKey(), entry.getValue()));
                }else {
                    continue;
                }
            }
        }

        return minRootHeap;
    }

    static class InnerItem {
        // 该字母出现的频率
        private int num;
        // 该字母
        private String key;

        public InnerItem( String key, int num) {
            this.num = num;
            this.key = key;
        }

        public int getValue() {
            return num;
        }

        public String getKey(){
            return key;
        }

        @Override
        public String toString() {
            return "InnerItem{" +
                    "num=" + num +
                    ", key='" + key + '\'' +
                    '}';
        }
        
    }

}
